/*************************************************************
*
* M3D_CLIP.CPP
*
* Polygon/line segment clipping & qualification (near/far 
* clipping, poly by poly & rect clipping, 
* point qualification by line * poly, ...)
*************************************************************/
#include <stdafx.h>

//#include <ap_comm.h>
#include <m3d/m3d.h>

#include <stdio.h>

// control CONVEX-checkings
// un-defining (commenting) this line can significantly speed up
// in DEBUG mode as CONVEX-polygon assertions will be switched off
// #define M3D_CHECK_CONVEX_POLY

//
// Static function
//
static int   _m3dGetClipRectCode (m2dPOLY *poly, m2dPOLY *polyRect, int *clipCode, int *nClipSide);
static int   _m2dClipPolyRect    (m2dPOLY *poly, m2dPOLY *polyRect, m2dPOLY *polyClip, int clipCode, int nClipSide);
static short _m2dGetPointCode    (m2dV *point, float x1, float y1, float x2, float y2);
static short _m3xyGetPointCode   (m3dV *point, float x1, float y1, float x2, float y2);

/*************************************************************
* m2dQualPointLine_A()
*
* IN:  v          - test point
*      lB         - line segment beginning
*      lE         - line segment end
*      accuracy   - accuracy
* OUT: M3D_LAY_IN, M3D_LAY_OUT, M3D_LAY_ON_BORDER
*
* Qualify a point by a given directed line - M3D_LAY_IN (LayLeft),
* M3D_LAY_OUT (LayRight), M3D_LAY_ON_BORDER (LayOnLine)
*************************************************************/
int m2dQualPointLine_A (const m2dV *v, const m2dV *lB, const m2dV *lE, float accuracy)
{
   register float d;
   d = lB->x*(lE->y - v->y) - lB->y*(lE->x - v->x) + lE->x*v->y - lE->y*v->x;
   if (d > accuracy)  {
      return M3D_LAY_IN;
   }
   if (d < -accuracy)  {
      return M3D_LAY_OUT;
   }
   return M3D_LAY_ON_BORDER;
}

int m3xzQualPointLine_A (const m3dV *v, const m3dV *lB, const m3dV *lE, float accuracy)
{
   register float d;

   d = (lE->x - lB->x)*v->z - lB->z*(lE->x - v->x) + lE->z*(lB->x - v->x);
#ifdef _DEBUG
   register float d1;
   d1 = lB->x*(lE->z - v->z) - lB->z*(lE->x - v->x) + lE->x*v->z - lE->z*v->x;
   float maxMult = max(m3dFAbs((lE->x - lB->x)*v->z), m3dFAbs(lB->z*(lE->x - v->x)));
   maxMult = max(maxMult, m3dFAbs(lE->z*(lB->x - v->x)));
   float maxMult2 = max(m3dFAbs(lB->x*(lE->z - v->z)), m3dFAbs(lB->z*(lE->x - v->x)));
   maxMult2 = max(maxMult2, m3dFAbs(lE->x*v->z));
   maxMult2 = max(maxMult2, m3dFAbs(lE->z*v->x));
   maxMult = max(maxMult2, maxMult);
   ASSERT(m3dFAbs(d1 - d) < max(maxMult*0.0001f, 0.001f));
#endif

   if (d > accuracy)  { 
      return M3D_LAY_IN;
   }
   if (d < -accuracy)  {
      return M3D_LAY_OUT;
   }
   return M3D_LAY_ON_BORDER;
}

int m3xyQualPointLine_A (const m3dV *v, const m3dV *lB, const m3dV *lE, float accuracy)
{
   register float d;
   d = lB->x*(lE->y - v->y) - lB->y*(lE->x - v->x) + lE->x*v->y - lE->y*v->x;
   if (d > accuracy)  {
      return M3D_LAY_IN;
   }
   if (d < -accuracy)  {
      return M3D_LAY_OUT;
   }
   return M3D_LAY_ON_BORDER;
}

int m3yzQualPointLine_A (const m3dV *v, const m3dV *lB, const m3dV *lE, float accuracy)
{
   register float d;
   d = lB->y*(lE->z - v->z) - lB->z*(lE->y - v->y) + lE->y*v->z - lE->z*v->y;
   if (d > accuracy)  {
      return M3D_LAY_IN;
   }
   if (d < -accuracy)  {
      return M3D_LAY_OUT;
   }
   return M3D_LAY_ON_BORDER;
}

/*************************************************************
* m2dClipPolyLSeg()
* 
* Clip a 2D polygon by a directed line segment
* IN:  poly     - polygon to be clipped
*      lB, lE   - directed line segment
* OUT: polyClip - clipped polygon
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clipping retcode)
*************************************************************/
int m2dClipPolyLSeg (m2dPOLY *poly, m2dV *lB, m2dV *lE,
                     m2dPOLY *polyClip)
{
   int  i;
   int  nout;
   int  position, position0, prevpos;
   int  n_inpoint; // number of points LayingIn
   int  n_bordpoint; // number of points LayingOnBorder
   int  qual[M3D_MAX_NVERT];

   // check that the clipping polygon is set properly
   ASSERT(m3dPolyNVert(poly) >= 3);

#ifdef M3D_CHECK_CONVEX_POLY
   // function works for convex polygons only
   ASSERT(m2dIsPolyConvex(poly));
#endif

   // check the number of vertices in polygons
   ASSERT(m3dPolyNVert(poly) > 0 && m3dPolyNVert(poly) <= M3D_MAX_NVERT);

   n_inpoint = n_bordpoint = 0;
   for (i = 0; i < m3dPolyNVert(poly); i++)  {
      qual[i] = m2dQualPointLine(m3dPolyVertex(poly,i),lB,lE);
      if (qual[i] == M3D_LAY_IN)  {
         n_inpoint++;
      }
      if (qual[i] == M3D_LAY_ON_BORDER)  {
         n_bordpoint++;
      }
   }

   if (n_inpoint == 0)  {
      // polygon lies outside
      return M3D_OUTSIDE;
   }

   if (n_inpoint + n_bordpoint == poly->nVert)  {
      // polygon lies inside
      *polyClip = *poly;
      return M3D_INSIDE;
   }

   position0 = prevpos = qual[0];
   if (position0 != M3D_LAY_OUT)  {
      *m3dPolyVertex(polyClip,0) = *m3dPolyVertex(poly,0);
      nout = 1;
   } else {
      nout = 0;
   }

   for (i = 1; i < m3dPolyNVert(poly); i++)  {
      position = qual[i];
      if (position == M3D_LAY_OUT)  {
         // point isn't in the POV
         if (prevpos == M3D_LAY_IN)  {
            // previous point was in the POV
            m2dIsectLineLine(m3dPolyVertex(poly,i-1),m3dPolyVertex(poly,i),
                             lB,lE,
                             m3dPolyVertex(polyClip,nout));
            nout++;
         }
      } else if (position == M3D_LAY_IN) {
         // point is in the POV
         if (prevpos == M3D_LAY_OUT)  {
            // previous point wasn't in the POV
            m2dIsectLineLine(m3dPolyVertex(poly,i-1),m3dPolyVertex(poly,i),
                             lB,lE,
                             m3dPolyVertex(polyClip,nout));
            nout++;
         }

         *m3dPolyVertex(polyClip,nout) = *m3dPolyVertex(poly,i);
         nout++;
      } else {
         // point is on the border of the POV
         ASSERT(position == M3D_LAY_ON_BORDER);
         *m3dPolyVertex(polyClip,nout) = *m3dPolyVertex(poly,i);
         nout++;
      }

      prevpos = position;
   }

   if (position0 == M3D_LAY_OUT)  {
      // point isn't in the POV
      if (prevpos == M3D_LAY_IN)  {
         // previous point was in the POV
         m2dIsectLineLine(m3dPolyVertex(poly,i-1),m3dPolyVertex(poly,0),
                          lB,lE,
                          m3dPolyVertex(polyClip,nout));
         nout++;
      }
   } else if (position0 == M3D_LAY_IN) {
      // point is in the POV
      if (prevpos == M3D_LAY_OUT)  {
         // previous point wasn't in the POV
         m2dIsectLineLine(m3dPolyVertex(poly,i-1),m3dPolyVertex(poly,0),
                          lB,lE,
                          m3dPolyVertex(polyClip,nout));
         nout++;
      }
   }

   ASSERT(nout >= 3);

   m3dPolyNVert(polyClip) = nout;

#ifdef M3D_CHECK_CONVEX_POLY
   ASSERT(m2dIsPolyConvex(polyClip));
#endif

   return M3D_ISECT;
}

/*************************************************************
* m2dClipPolyPoly()
* 
* Clip a 2D polygon by another one (both of then are to
* be CCW-oriented). Satherland algorithm is used.
* IN:  poly       - polygon to be clipped
*      polyClipBy - clipping polygon
* OUT: polyClip   - clipped polygon
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip retcode)
*************************************************************/
int m2dClipPolyPoly (m2dPOLY *poly, m2dPOLY *polyClipBy, m2dPOLY *polyClip)
{
   int i, rc;
   m2dPOLY polySrc;

   // check that the clipping rectangle is set properly
   ASSERT(m3dPolyNVert(poly) >= 3);

   // assert that both polygons are CCW-oriented
   ASSERT(m2dQualPointLine_A(m3dPolyVertex(poly,2),
                             m3dPolyVertex(poly,0),
                             m3dPolyVertex(poly,1),
                             10*M3D_EPSILON) != M3D_LAY_OUT);
   ASSERT(m2dQualPointLine_A(m3dPolyVertex(polyClipBy,2),
                             m3dPolyVertex(polyClipBy,0),
                             m3dPolyVertex(polyClipBy,1),
                             10*M3D_EPSILON) != M3D_LAY_OUT);

   // this is done to prevent "poly" modifications
   polySrc = *poly;

   for (i = 0; i < m3dPolyNVert(polyClipBy)-1; i++)  {
      rc = m2dClipPolyLSeg(&polySrc,
                           m3dPolyVertex(polyClipBy,i),
                           m3dPolyVertex(polyClipBy,i+1),
                           polyClip);
      if (rc == M3D_OUTSIDE) {
         return rc;
      }
      polySrc = *polyClip;
   }

   rc = m2dClipPolyLSeg(&polySrc,
                        m3dPolyVertex(polyClipBy,i),
                        m3dPolyVertex(polyClipBy,0),
                        polyClip);
   if (rc == M3D_OUTSIDE) {
      return rc;
   }

   // it can happen that some vertices concide
   if (!m2dDropPolyRepeatVertices(polyClip))  {
      return M3D_OUTSIDE;
   }

   return rc;
}

/*************************************************************
* m2dIsBelongPointTri_A ()
*
* IN:  tri   - test triangle
*      v     - test point
* RET: TRUE  - point 'v' belongs to triangle 'tri'
*      FALSE - otherwise
*
* Checks whether the 2D point belongs to the 2D triangle
* This function works for both CCW- and CW-oriented triangle
*************************************************************/
BOOL m2dIsBelongPointTri_A (m2dTRI *tri,  m2dV *v, float accuracy)
{
   BOOL rc = TRUE;
#ifdef _DEBUG
   m2dPOLY poly;
   poly.nVert = 3;
   poly.vert[0] = tri->v1;
   poly.vert[1] = tri->v2;
   poly.vert[2] = tri->v3;

   rc = m2dIsBelongPointPoly_A(&poly, v, accuracy);
#endif

   float  kA, kB;
   m2dTriGetBasisCoord(tri, v, &kA, &kB);

   if (kA < -accuracy || kB < -accuracy || kA + kB > 1.f + accuracy) {

#ifdef _DEBUG
      ASSERT(!rc);
#endif

      return FALSE;
   }

#ifdef _DEBUG
   ASSERT(rc);
#endif
   return TRUE;
}

/*************************************************************
* m2dIsBelongPointPoly()
*
* IN:  poly  - test polygon
*      v     - test point
* RET: TRUE  - point 'v' belongs to polygon 'poly'
*      FALSE - otherwise
*
* Checks whether the 2D point belongs to the 2D polygon
* This function works for both CCW- and CW-oriented polygons
*************************************************************/
BOOL m2dIsBelongPointPoly_A (m2dPOLY *poly, m2dV *v, float accuracy)
{
   int   i;
   int   qual;

   // check the number of vertices in polygons
   ASSERT(m3dPolyNVert(poly) > 0 && m3dPolyNVert(poly) <= M3D_MAX_NVERT);

   if (m2dQualPointLine_A(m3dPolyVertex(poly,2),m3dPolyVertex(poly,0),m3dPolyVertex(poly,1),accuracy) == M3D_LAY_OUT)  {
      // isOrientLeft = FALSE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         // check that for each side the point lies inside the poly
         // formula:
         //
         // |x1 y1 1|      > 0 then (x3,y3) lies to the left of
         // |x2 y2 1| ? 0           (x1,y1)-(x2,y2)
         // |x3 y3 1|

         qual = m2dQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_IN)  {
            return FALSE;
         }
      }
      qual = m2dQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_IN)  {
         return FALSE;
      }
      return TRUE;
   } else {
      // isOrientLeft = TRUE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         // check that for each side the point lies inside the poly
         // formula:
         //
         // |x1 y1 1|      > 0 then (x3,y3) lies to the left of
         // |x2 y2 1| ? 0           (x1,y1)-(x2,y2)
         // |x3 y3 1|

         qual = m2dQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_OUT)  {
            return FALSE;
         }
      }
      qual = m2dQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_OUT)  {
         return FALSE;
      }
      return TRUE;
   }
}

/*************************************************************
* m3xzIsBelongPointPoly_A()
*
*************************************************************/
BOOL m3xzIsBelongPointPoly_A (m3dPOLY *poly, m3dV *v, float accuracy)
{
   int   i;
   int   qual;

   // check the number of vertices in polygons
   ASSERT(m3dPolyNVert(poly) > 0 && m3dPolyNVert(poly) <= M3D_MAX_NVERT);

   if (m3xzQualPointLine_A(m3dPolyVertex(poly,2),m3dPolyVertex(poly,0),m3dPolyVertex(poly,1),accuracy) == M3D_LAY_OUT)  {
      // isOrientLeft = FALSE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         qual = m3xzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_IN)  {
            return FALSE;
         }
      }
      qual = m3xzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_IN)  {
         return FALSE;
      }
      return TRUE;
   } else {
      // isOrientLeft = TRUE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         qual = m3xzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_OUT)  {
            return FALSE;
         }
      }
      qual = m3xzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_OUT)  {
         return FALSE;
      }
      return TRUE;
   }
}

/*************************************************************
* m3xyIsBelongPointPoly_A()
*
*************************************************************/
BOOL m3xyIsBelongPointPoly_A (m3dPOLY *poly, m3dV *v, float accuracy)
{
   int   i;
   int   qual;

   // check the number of vertices in polygons
   ASSERT(m3dPolyNVert(poly) > 0 && m3dPolyNVert(poly) <= M3D_MAX_NVERT);

   if (m3xyQualPointLine_A(m3dPolyVertex(poly,2),m3dPolyVertex(poly,0),m3dPolyVertex(poly,1),accuracy) == M3D_LAY_OUT)  {
      // isOrientLeft = FALSE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         qual = m3xyQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_IN)  {
            return FALSE;
         }
      }
      qual = m3xyQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_IN)  {
         return FALSE;
      }
      return TRUE;
   } else {
      // isOrientLeft = TRUE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         qual = m3xyQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_OUT)  {
            return FALSE;
         }
      }
      qual = m3xyQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_OUT)  {
         return FALSE;
      }
      return TRUE;
   }
}

/*************************************************************
* m3yzIsBelongPointPoly_A()
*
*************************************************************/
BOOL m3yzIsBelongPointPoly_A (m3dPOLY *poly, m3dV *v, float accuracy)
{
   int   i;
   int   qual;

   if (m3yzQualPointLine_A(m3dPolyVertex(poly,2),m3dPolyVertex(poly,0),m3dPolyVertex(poly,1),accuracy) == M3D_LAY_OUT)  {
      // isOrientLeft = FALSE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         qual = m3yzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_IN)  {
            return FALSE;
         }
      }
      qual = m3yzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_IN)  {
         return FALSE;
      }
      return TRUE;
   } else {
      // isOrientLeft = TRUE;
      for (i = 0; i < m3dPolyNVert(poly) - 1; i++)  {
         qual = m3yzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,i+1),accuracy);
         if (qual == M3D_LAY_OUT)  {
            return FALSE;
         }
      }
      qual = m3yzQualPointLine_A(v,m3dPolyVertex(poly,i),m3dPolyVertex(poly,0),accuracy);
      if (qual == M3D_LAY_OUT)  {
         return FALSE;
      }
      return TRUE;
   }
}

/*************************************************************
* m3dIsBelongPointPoly_A()
*
* IN:  poly  - test polygon
*      v     - test point
*      norm  - polygon normal (can be NULL)
* RET: TRUE  - point 'v' belongs to polygon 'poly'
*      FALSE - otherwise
*
* Check if a point belongs to 'poly'. To check we ortho-project 
* 'poly' to either XZ, XY or YZ plane (one of the projections is to be
* non-degenerate polygon). Then simple check of 2D case is applicable.
*
* To select a plane for projection we find such one that 
* the poly normal has greatest component along the corresponding
* axis. This is to minimize numerical errors in 2D case.
*************************************************************/
BOOL m3dIsBelongPointPoly_A (m3dPOLY *poly, m3dV *v, m3dV *norm, float accuracy)
{
   m3dV normTmp;

   if (!norm) {
      m3dGetPolyNormal(poly, &normTmp);
      norm = &normTmp;
   }

   // point must belong to polygon's plane
   ASSERT(m3dDistPointPlane(v, poly, norm) < .001f);

   if (m3dFAbs(norm->x) > m3dFAbs(norm->y))  {
      if (m3dFAbs(norm->x) > m3dFAbs(norm->z))  {
         // project to YZ plane
         return m3yzIsBelongPointPoly_A(poly,v,accuracy);
      } else {
         // project to XY plane
         return m3xyIsBelongPointPoly_A(poly,v,accuracy);
      }
   } else {
      if (m3dFAbs(norm->y) > m3dFAbs(norm->z))  {
         // project to XZ plane
         return m3xzIsBelongPointPoly_A(poly,v,accuracy);
      } else {
         // project to XY plane
         return m3xyIsBelongPointPoly_A(poly,v,accuracy);
      }
   }

   // one of the projection should have been selected
   ASSERT(FALSE);
}

/*************************************************************
* m3dClipPolyNearPlane()
*
* Clip the polygon by near plane
* IN:  poly     - polygon to be clipped
*      dist     - distance to near plane
* OUT: polyClip - clipped polygon
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip retcode)
*************************************************************/
int m3dClipPolyNearPlane (m3dPOLY *poly, float dist, m3dPOLY* polyClip)
{
   int   rc, i, nClip;
   m3dV  point1, point2;

   // check that the clipping rectangle is set properly
   ASSERT(poly->nVert >= 3);

   rc = M3D_INSIDE;

   nClip = 0;
   for (i=0; i<m3dPolyNVert(poly); i++) {
      point1 = *m3dPolyVertex(poly,i);
      point2 = *m3dPolyVertex(poly,(i == m3dPolyNVert(poly)-1) ? 0 : i+1);

      if (point1.z >= dist) {
         // first point is inside: add it to list
         if (nClip == 0 || !m3dIsEqualPoint_A(m3dPolyVertex(polyClip, nClip-1), &point1, M3D_EPSILON)) {
            *(m3dPolyVertex(polyClip, nClip++)) = point1; // add first point to list
         }

         if (point2.z < dist) {
            // second point outside: clip & add
            point2.x = point1.x + (point2.x - point1.x)*(dist - point1.z)/(point2.z - point1.z);
            point2.y = point1.y + (point2.y - point1.y)*(dist - point1.z)/(point2.z - point1.z);
            point2.z = dist;
            if (nClip == 0 || !m3dIsEqualPoint_A(m3dPolyVertex(polyClip, nClip-1), &point2, M3D_EPSILON)) {
               *(m3dPolyVertex(polyClip, nClip++)) = point2;
            }
            rc = M3D_ISECT;
         }
         continue;
      } else {
         // first point in outside: check second point
         if (point2.z < dist) {
            // second point is outside: do nothing
            continue;
         } else {
            // second point is inside: clip & add first point
            point1.x = point1.x + (point2.x - point1.x)*(dist - point1.z)/(point2.z - point1.z);
            point1.y = point1.y + (point2.y - point1.y)*(dist - point1.z)/(point2.z - point1.z);
            point1.z = dist;
            if (nClip == 0 || !m3dIsEqualPoint_A(m3dPolyVertex(polyClip, nClip-1), &point1, M3D_EPSILON)) {
               *(m3dPolyVertex(polyClip, nClip++)) = point1; // add first point to list
            }
            rc = M3D_ISECT;
         }
      }
   }

   if (nClip < 3) {
      // polygon outside the clip rectangle: don't draw
      return M3D_OUTSIDE;
   }
   m3dPolyNVert(polyClip) = nClip;

   return rc;
}

/*************************************************************
* m3dClipPolyFarPlane()
*
* Clip the polygon by near plane
* IN:  poly     - polygon to be clipped
*      dist     - distance to near plane
* OUT: polyClip - clipped polygon
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip retcode)
*************************************************************/
int m3dClipPolyFarPlane (m3dPOLY *poly, float dist, m3dPOLY *polyClip)
{
   int   i, rc, nClip;
   m3dV  point1, point2;

   // check that the clipping rectangle is set properly
   ASSERT(poly->nVert >= 3);

   rc = M3D_INSIDE;

   nClip = 0;
   for (i = 0; i < m3dPolyNVert(poly); i++) {
      point1 = *m3dPolyVertex(poly,i);
      point2 = *m3dPolyVertex(poly,(i == m3dPolyNVert(poly)-1) ? 0 : i+1);

      if (point1.z <= dist) {
         // first point is inside: add it to list
         if (nClip == 0 || !m3xyIsEqualPoint_A(m3dPolyVertex(polyClip, nClip-1), &point1, M3D_EPSILON)) {
            *(m3dPolyVertex(polyClip, nClip++)) = point1; // add first point to list
         }

         if (point2.z > dist) {
            // second point outside: clip & add
            point2.x = point1.x + (point2.x - point1.x)*(dist - point1.z)/(point2.z - point1.z);
            point2.y = point1.y + (point2.y - point1.y)*(dist - point1.z)/(point2.z - point1.z);
            point2.z = dist;
            if (nClip == 0 || !m3dIsEqualPoint_A(m3dPolyVertex(polyClip, nClip-1), &point2, M3D_EPSILON)) {
               *(m3dPolyVertex(polyClip, nClip++)) = point2;
            }
            rc = M3D_ISECT;
         }
         continue;
      } else {
         // first point in outside: check second point
         if (point2.z > dist) {
            // second point is outside: do nothing
            continue;
         } else {
            // second point is inside: clip & add first point
            point1.x = point1.x + (point2.x - point1.x)*(dist - point1.z)/(point2.z - point1.z);
            point1.y = point1.y + (point2.y - point1.y)*(dist - point1.z)/(point2.z - point1.z);
            point1.z = dist;
            if (nClip == 0 || !m3dIsEqualPoint_A(m3dPolyVertex(polyClip, nClip-1), &point1, M3D_EPSILON)) {
               *(m3dPolyVertex(polyClip, nClip++)) = point1; // add first point to list
            }
            rc = M3D_ISECT;
         }
      }
   }

   if (nClip < 3) {
      // polygon outside the clip rectangle: don't draw
      return M3D_OUTSIDE;
   }
   m3dPolyNVert(polyClip) = nClip;

   return rc;
}

/*************************************************************
* m3dClipPolyPlane ()
*
* Clip the polygon by arbitrary plane
* IN:  poly     - polygon to be clipped
*      point    - plane point
*      norm     - plane normal
* OUT: polyClip - clipped polygon
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip retcode)
*************************************************************/
int m3dClipPolyPlane (const m3dPOLY *poly, const m3dV *point, const m3dV *norm, m3dPOLY* polyClip)
{
   m3dPOLY polyShifted;
   float   dotProd[M3D_MAX_NVERT], coeff;
   int     rc, i, nClip, ind1, ind2;

   // check that the clipping rectangle is set properly
   ASSERT(poly->nVert >= 3 && poly->nVert <= 7);

   if (point) {
      // shift polygon into plane CS if needed
      for (i = 0; i < poly->nVert; i ++) {
         m3dSubtractVector(&poly->vert[i], point, &polyShifted.vert[i]);
      }
      polyShifted.nVert = poly->nVert;
      poly = &polyShifted;
   }

   for (i = 0; i < poly->nVert; i ++) {
      dotProd[i] = m3dDotProduct(&poly->vert[i], norm);
   }

   rc = M3D_INSIDE;

   nClip = 0;
   for (ind1 = 0; ind1 < poly->nVert; ind1 ++) {
      ind2 = (ind1 == m3dPolyNVert(poly)-1) ? 0 : ind1 + 1;
      
      if (dotProd[ind1] >= 0.f) {
         // first point is inside: add it to list
         polyClip->vert[nClip ++] = poly->vert[ind1]; 

         if (dotProd[ind2] < 0.f) {
            // second point outside: clip & add
            coeff = dotProd[ind1] / (dotProd[ind1] - dotProd[ind2]);
            if (coeff > 100.f*M3D_EPSILON) {
               // clipped point doesn't coincide with previously added point, add it
               m3dLineCombine(&poly->vert[ind1], 1.f - coeff, &poly->vert[ind2], coeff, &polyClip->vert[nClip ++]);
            }
            rc = M3D_ISECT;
         }
         continue;
      } else {
         // first point in outside: check second point
         if (dotProd[ind2] < 0.f) {
            // second point is outside: do nothing
            continue;
         } else {
            // second point is inside: clip & add first point
            coeff = dotProd[ind1] / (dotProd[ind1] - dotProd[ind2]);
            if (coeff < 1.f - 100.f*M3D_EPSILON) {
               // clipped point doesn't coincide with previously added point, add it
               m3dLineCombine(&poly->vert[ind1], 1.f - coeff, &poly->vert[ind2], coeff, &polyClip->vert[nClip ++]);
            }
            rc = M3D_ISECT;
         }
      }
   }

   if (nClip < 3) {
      // polygon outside the clip rectangle: don't draw
      return M3D_OUTSIDE;
   }
   ASSERT(poly->nVert >= 3 && poly->nVert <= 8);

#ifdef _DEBUG
   for (i = 0; i < nClip; i ++) {
      dotProd[i] = m3dDotProduct(&polyClip->vert[i], norm);
      ASSERT(dotProd[i] > -1000*M3D_EPSILON);
   }
#endif

   if (point) {
      // shift polygon back
      for (i = 0; i < nClip; i ++) {
         _m3dAddVector(&polyClip->vert[i], point);
      }
   }
   polyClip->nVert = nClip;
   return rc;
}


/*************************************************************
* m2dDropPolyRepeatVertices()
* m3dDropPolyRepeatVertices()
*
* Drop polygon vertices that are repeated
*************************************************************/
BOOL m2dDropPolyRepeatVertices (m2dPOLY *poly2D)
{
   int i;

   for (i = 0; i < m3dPolyNVert(poly2D); i++)  {
      if (m2dIsEqualPoint_A(m3dPolyVertex(poly2D,i),
                            m3dPolyVertex(poly2D,(i+1)%m3dPolyNVert(poly2D)),
                            10000*M3D_EPSILON))  {
         if (i < m3dPolyNVert(poly2D)-1) {
            memcpy(m3dPolyVertex(poly2D, i),
                   m3dPolyVertex(poly2D, i+1), sizeof(m2dV)*(m3dPolyNVert(poly2D) - (i+1)));
         }
         m3dPolyNVert(poly2D)--;
         i--; // To continue from current point
      }
   }

   if (m3dPolyNVert(poly2D) < 3)  {
      return FALSE;
   }

   return TRUE;
}

BOOL m3dDropPolyRepeatVertices (m3dPOLY *poly3D)
{
   int i;

   for (i = 0; i < m3dPolyNVert(poly3D); i++)  {
      if (m3dIsEqualPoint_A(m3dPolyVertex(poly3D,i),
                            m3dPolyVertex(poly3D,(i+1)%m3dPolyNVert(poly3D)),
                            10000*M3D_EPSILON))  {
         if (i < m3dPolyNVert(poly3D)-1) {
            memcpy(m3dPolyVertex(poly3D, i),
                   m3dPolyVertex(poly3D, i+1), sizeof(m3dV)*(m3dPolyNVert(poly3D) - (i+1)));
         }

         m3dPolyNVert(poly3D)--;
         i--; // To continue from current point
      }
   }

   if (m3dPolyNVert(poly3D) < 3)  {
      return FALSE;
   }

   return TRUE;
}

/*************************************************************
* _m2dClipPolyRect()
*
* Clip poly2D by rect2D
* This is faster then the general polygon clipping procedure
* IN:  poly      - source poly
*      polyRect  - clip rectangle
*      clipCode  - precomputed clipCode
*      nClipSide - number of rectangle sides that are isected
*                  by a given polygon
* OUT: polyClip  - clipped poly
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip result)
*************************************************************/
static int _m2dClipPolyRect (m2dPOLY *poly, m2dPOLY *polyRect, m2dPOLY *polyClip, int clipCode, int nClipSide)
{
   m2dPOLY         result1, result2, result3;
   m2dPOLY        *pCurResult, *pNextResult;
   int             rc, i, nClip = 0;
   m2dV            point1, point2;
   float           t, x1, y1, x2, y2; // clip rectangle boundaries

   ASSERT(m3dPolyNVert(polyRect) == 4);
   // otherwise what for to call this function?
   ASSERT(clipCode  != 0);
   ASSERT(nClipSide != 0);

   // Generate a clip rectangle
   x1 = m3dPolyVertexX(polyRect, 0);
   y1 = m3dPolyVertexY(polyRect, 0);
   x2 = m3dPolyVertexX(polyRect, 2);
   y2 = m3dPolyVertexY(polyRect, 2);

   if (x1 > x2) {
      t = x1;
      x1 = x2;
      x2 = t;
   }
   if (y1 > y2) {
      t = y1;
      y1 = y2;
      y2 = t;
   }
   
   rc = M3D_INSIDE;

   // =====================
   // Clipping by left line
   // =====================
   pCurResult = poly;

   if (clipCode & M3D_CODE_LEFT) {
      pNextResult = (nClipSide == 1) ? polyClip : &result1;
      nClip = 0;
      for (i=0; i<m3dPolyNVert(pCurResult); i++) {
         point1 = m3dPolyVertList(pCurResult)[i];
         point2 = m3dPolyVertList(pCurResult)[(i == m3dPolyNVert(pCurResult)-1) ? 0 : i+1];

         if (point1.x >= x1) {
            // first point is inside: add it to list
            if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
               *(m3dPolyVertex(pNextResult, nClip++)) = point1; // add first point to list
            }

            if (point2.x < x1) {
               // second point outside: clip & add
               point2.y = point1.y + (point2.y - point1.y)*(x1 - point1.x)/(point2.x - point1.x);
               point2.x = x1;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point2, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point2;
               }
               rc = M3D_ISECT;
            }
            continue;
         } else {
            // first point in outside: check second point
            if (point2.x < x1) {
               // second point is outside: do nothing
               continue;
            } else {
               // second point is inside: clip & add first point
               point1.y = point1.y + (point2.y - point1.y)*(x1 - point1.x)/(point2.x - point1.x);
               point1.x = x1;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point1; // add first point to list
               }
               rc = M3D_ISECT;
            }
         }
      }
      if (nClip < 3) {
         // polygon outside the clip rectangle: don't draw
         return M3D_OUTSIDE;
      }
      m3dPolyNVert(pNextResult) = nClip;
      pCurResult = pNextResult;
      nClipSide--;
   } 

   // ====================
   // Clipping by top line
   // ====================
   if (clipCode & M3D_CODE_BELOW) {
      pNextResult = (nClipSide == 1) ? polyClip : &result2;
      nClip = 0;
      for (i=0; i<m3dPolyNVert(pCurResult); i++) {
         point1 = m3dPolyVertList(pCurResult)[i];
         point2 = m3dPolyVertList(pCurResult)[(i == m3dPolyNVert(pCurResult)-1) ? 0 : i+1];

         if (point1.y >= y1) {
            // first point is inside: add it to list
            if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
               *(m3dPolyVertex(pNextResult, nClip++)) = point1; // add first point to list
            }

            if (point2.y < y1) {
               // second point outside: clip & add
               point2.x = point1.x + (point2.x - point1.x)*(y1 - point1.y)/(point2.y - point1.y);
               point2.y = y1;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point2, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point2;
               }
               rc = M3D_ISECT;
            }
            continue;
         } else {
            // first point in outside: check second point
            if (point2.y < y1) {
               // second point is outside: do nothing
               continue;
            } else {
               // second point is inside: clip & add first point
               point1.x = point1.x + (point2.x - point1.x)*(y1 - point1.y)/(point2.y - point1.y);
               point1.y = y1;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point1; // add first point to list
               }
               rc = M3D_ISECT;
            }
         }
      }

      if (nClip < 3) {
         // polygon outside the clip rectangle: don't draw
         return M3D_OUTSIDE;
      }
      m3dPolyNVert(pNextResult) = nClip;
      pCurResult = pNextResult;
      nClipSide--;
   }

   // ======================
   // Clipping by right line
   // ======================
   if (clipCode & M3D_CODE_RIGHT) {
      pNextResult = (nClipSide == 1) ? polyClip : &result3;
      nClip = 0;
      for (i=0; i<m3dPolyNVert(pCurResult); i++) {
         point1 = m3dPolyVertList(pCurResult)[i];
         point2 = m3dPolyVertList(pCurResult)[(i == m3dPolyNVert(pCurResult)-1) ? 0 : i+1];

         if (point1.x <= x2) {
            // first point is inside: add it to list
            if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
               *(m3dPolyVertex(pNextResult, nClip++)) = point1; // add first point to list
            }

            if (point2.x > x2) {
               // second point outside: clip & add
               point2.y = point1.y + (point2.y - point1.y)*(x2 - point1.x)/(point2.x - point1.x);
               point2.x = x2;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point2, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point2;
               }
               rc = M3D_ISECT;
            }
            continue;
         } else {
            // first point in outside: check second point
            if (point2.x > x2) {
               // second point is outside: do nothing
               continue;
            } else {
               // second point is inside: clip & add first point
               point1.y = point1.y + (point2.y - point1.y)*(x2 - point1.x)/(point2.x - point1.x);
               point1.x = x2;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point1; // add first point to list
               }
               rc = M3D_ISECT;
            }
         }
      }
      if (nClip < 3) {
         // polygon outside the clip rectangle: don't draw
         return M3D_OUTSIDE;
      }
      m3dPolyNVert(pNextResult) = nClip;
      pCurResult = pNextResult;
      nClipSide--;
   }

   // =======================
   // Clipping by bottom line
   // =======================
   if (clipCode & M3D_CODE_ABOVE) {      
      pNextResult = polyClip;
      nClip = 0;
      for (i=0; i<m3dPolyNVert(pCurResult); i++) {
         point1 = m3dPolyVertList(pCurResult)[i];
         point2 = m3dPolyVertList(pCurResult)[(i == m3dPolyNVert(pCurResult)-1) ? 0 : i+1];

         if (point1.y <= y2) {
            // first point is inside: add it to list
            if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
               *(m3dPolyVertex(pNextResult, nClip++))  = point1; // add first point to list
            }

            if (point2.y > y2) {
               // second point outside: clip & add
               point2.x = point1.x + (point2.x - point1.x)*(y2 - point1.y)/(point2.y - point1.y);
               point2.y = y2;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point2, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point2;
               }
               rc = M3D_ISECT;
            }
            continue;
         } else {
            // first point in outside: check second point
            if (point2.y > y2) {
               // second point is outside: do nothing
               continue;
            } else {
               // second point is inside: clip & add first point
               point1.x = point1.x + (point2.x - point1.x)*(y2 - point1.y)/(point2.y - point1.y);
               point1.y = y2;
               if (nClip == 0 || !m2dIsEqualPoint_A(m3dPolyVertex(pNextResult, nClip-1), &point1, M3D_EPSILON_2)) {
                  *(m3dPolyVertex(pNextResult, nClip++)) = point1; // add first point to list
               }
               rc = M3D_ISECT;
            }
         }
      }
      if (nClip < 3) {
         return M3D_OUTSIDE;
      }
      m3dPolyNVert(pNextResult) = nClip;
      nClipSide--;
   }
   // Check first and last points for coincidence
   if (m2dIsEqualPoint_A(m3dPolyVertex(polyClip, nClip-1), m3dPolyVertex(polyClip, 0), M3D_EPSILON_2)) {
      m3dPolyNVert(polyClip)--;
      if (m3dPolyNVert(polyClip) < 3) {
         return M3D_OUTSIDE;
      }
   }

   ASSERT(nClipSide == 0);
   ASSERT(rc != M3D_INSIDE);
   return rc;
}

/*************************************************************
* _m3dGetClipRectCode()
*
* Get clipping code for clipping poly2D by rect2D
* IN:  poly      - source poly
*      polyRect  - clip rectangle
* OUT: clipCode  - precomputed clipCode
*      nClipSide - number of rectangle sides that are isected
*                  by a given polygon
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip result)
*************************************************************/
static int _m3dGetClipRectCode (m2dPOLY *poly, m2dPOLY *polyRect, int *clipCode, int *nClipSide)
{
   int             i, _clipCode, _nClipSide;
   float           t, x1, y1, x2, y2; // clip rectangle boundaries

   ASSERT(m3dPolyNVert(polyRect) == 4);

   // Generate a clip rectangle
   x1 = m3dPolyVertexX(polyRect, 0);
   y1 = m3dPolyVertexY(polyRect, 0);
   x2 = m3dPolyVertexX(polyRect, 2);
   y2 = m3dPolyVertexY(polyRect, 2);

   if (x1 > x2) {
      t = x1;
      x1 = x2;
      x2 = t;
   }
   if (y1 > y2) {
      t = y1;
      y1 = y2;
      y2 = t;
   }

   // 
   // Calculate clipping codes
   // 
   _clipCode = _nClipSide = 0;
   for (i=0; i<m3dPolyNVert(poly); i++) {
      if (m3dPolyVertexX(poly,i) < x1) {
         _clipCode |= M3D_CODE_LEFT;
         _nClipSide++;
         break;
      }
   }
   for (i=0; i<m3dPolyNVert(poly); i++) {
      if (m3dPolyVertexX(poly,i) > x2) {
         _clipCode |= M3D_CODE_RIGHT;
         _nClipSide++;
         break;
      }
   }
   for (i=0; i<m3dPolyNVert(poly); i++) {
      if (m3dPolyVertexY(poly,i) < y1) {
         _clipCode |= M3D_CODE_BELOW;
         _nClipSide++;
         break;
      }
   }
   for (i=0; i<m3dPolyNVert(poly); i++) {
      if (m3dPolyVertexY(poly,i) > y2) {
         _clipCode |= M3D_CODE_ABOVE;
         _nClipSide++;
         break;
      }
   }
   *clipCode  = _clipCode;
   *nClipSide = _nClipSide;
   if (_clipCode == 0) {
      return M3D_INSIDE;
   }
   return M3D_ISECT;
}

/*************************************************************
* m2dClipPolyRect()
*
* Clip poly2D by rect2D
* This is faster then the general polygon clipping procedure
* IN:  poly      - source poly
*      polyRect  - clip rectangle
*      clipCode  - precomputed clipCode
*      nClipSide - number of rectangle sides that are isected
*                  by a given polygon
* OUT: polyClip  - clipped poly
* Return:     M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip result)
*************************************************************/
int m2dClipPolyRect (m2dPOLY *poly, m2dPOLY *polyRect, m2dPOLY *polyClip)
{
   int rc;
   int clipCode, nClipSide;

   ASSERT(m3dPolyNVert(polyRect) == 4);

   rc = _m3dGetClipRectCode(poly, polyRect, &clipCode, &nClipSide);
   if (rc == M3D_OUTSIDE) {
      return rc;
   }
   if (rc == M3D_INSIDE) {
      *polyClip = *poly;
      return rc;
   }

   return _m2dClipPolyRect(poly, polyRect, polyClip, clipCode, nClipSide);
}
/*************************************************************
* m2dClipTriRect()
*
* Clip 2D triangle by rect2D
*************************************************************/
int m2dClipTriRect (m2dTRI *tri, m2dPOLY *polyRect, m2dPOLY *polyClip)
{
   m2dPOLY   poly;

   poly = *tri;
   return m2dClipPolyRect(&poly, polyRect, polyClip);
}



/*************************************************************
* m2dClipLSegRect()
*
* Clip line segment by 2D rectangle
* IN : lB, lE         - line segment
*      polyRect       - clipping rectangle
* OUT: lBClip, lEClip - clipped line segment
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip retcode)
*************************************************************/
int m2dClipLSegRect (m2dV *lB, m2dV *lE, m2dPOLY *polyRect, m2dV *lBClip, m2dV *lEClip)
{
   short   code1, code2;
   float   t, x1, y1, x2, y2; // clip rectangle boundaries
   int     rc;

   ASSERT(m3dPolyNVert(polyRect) == 4);

   // Generate a clip rectangle
   x1 = m3dPolyVertexX(polyRect, 0);
   y1 = m3dPolyVertexY(polyRect, 0);
   x2 = m3dPolyVertexX(polyRect, 2);
   y2 = m3dPolyVertexY(polyRect, 2);

   if (x1 > x2) {
      t = x1;
      x1 = x2;
      x2 = t;
   }
   if (y1 > y2) {
      t = y1;
      y1 = y2;
      y2 = t;
   }
   *lBClip = *lB;
   *lEClip = *lE;

   rc = M3D_INSIDE;

   code1 = _m2dGetPointCode(lBClip, x1, y1, x2, y2);
   code2 = _m2dGetPointCode(lEClip, x1, y1, x2, y2);

   while (code1 | code2) {
      rc = M3D_ISECT;
      if (code1 & code2) { // Line lays outside rectangle
         return M3D_OUTSIDE;
      }
      if (code1 & M3D_CODE_LEFT) {         // lB->x < x1
         lBClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x1 - lBClip->x)/(lEClip->x - lBClip->x);
         lBClip->x = x1;
      } else if (code1 & M3D_CODE_BELOW) { // lB->y < y1
         lBClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y1 - lBClip->y)/(lEClip->y - lBClip->y);
         lBClip->y = y1;
      } else if (code1 & M3D_CODE_RIGHT) { // lBClip->x > x2
         lBClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x2 - lBClip->x)/(lEClip->x - lBClip->x);
         lBClip->x = x2;
      } else if (code1 & M3D_CODE_ABOVE) { // lBClip->y > y2
         lBClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y2 - lBClip->y)/(lEClip->y - lBClip->y);
         lBClip->y = y2;
      }
      code1 = _m2dGetPointCode(lBClip, x1, y1, x2, y2);
      if (code1 & code2) { // Line lays outside rectangle
         return M3D_OUTSIDE;
      }

      if (code2 & M3D_CODE_LEFT) {         // lEClip->x < x1
         lEClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x1 - lBClip->x)/(lEClip->x - lBClip->x);
         lEClip->x = x1;
      } else if (code2 & M3D_CODE_BELOW) { // lEClip->y < y1
         lEClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y1 - lBClip->y)/(lEClip->y - lBClip->y);
         lEClip->y = y1;
      } else if (code2 & M3D_CODE_RIGHT) { // lEClip->x > x2
         lEClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x2 - lBClip->x)/(lEClip->x - lBClip->x);
         lEClip->x = x2;
      } else if (code2 & M3D_CODE_ABOVE) { // lEClip->y > y2
         lEClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y2 - lBClip->y)/(lEClip->y - lBClip->y);
         lEClip->y = y2;
      }
      code2 = _m2dGetPointCode(lEClip, x1, y1, x2, y2);
   }
   return rc;
}

/*************************************************************
* m3xyClipLSegRect()
*
* Clip 3D line segment by 3D-XY rectangle
* IN  : lB, lE         - line segment
*       polyRect       - clipping rectangle
* OUT : lBClip, lEClip - clipped line segment
* RET : M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip retcode)
* NOTE: This function performs proper interpolation of z values
*       along the line segment being clipped
*************************************************************/
int m3xyClipLSegRect (m3dV *lB, m3dV *lE, m2dPOLY *polyRect, m3dV *lBClip, m3dV *lEClip)
{
   short  code1, code2;
   float  t, x1, y1, x2, y2; // clip rectangle boundaries
   int    rc;
#ifdef _DEBUG
   short  nRepeat = 0;
#endif

   ASSERT(m3dPolyNVert(polyRect) == 4);

   // Generate a clip rectangle
   x1 = m3dPolyVertexX(polyRect, 0);
   y1 = m3dPolyVertexY(polyRect, 0);
   x2 = m3dPolyVertexX(polyRect, 2);
   y2 = m3dPolyVertexY(polyRect, 2);

   if (x1 > x2) {
      t = x1;
      x1 = x2;
      x2 = t;
   }
   if (y1 > y2) {
      t = y1;
      y1 = y2;
      y2 = t;
   }
   *lBClip = *lB;
   *lEClip = *lE;

   rc = M3D_INSIDE;

   code1 = _m3xyGetPointCode(lBClip, x1, y1, x2, y2);
   code2 = _m3xyGetPointCode(lEClip, x1, y1, x2, y2);

   while (code1 | code2) {
#ifdef _DEBUG
      if (nRepeat++ > 100) {
         ASSERT(FALSE);
      }
#endif
      rc = M3D_ISECT;

      if (code1 & code2) { // Line lays outside rectangle
         return M3D_OUTSIDE;
      }
      if (code1 & M3D_CODE_LEFT) {         // lB->x < x1
         lBClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(x1 - lBClip->x)/(lEClip->x - lBClip->x));
         lBClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x1 - lBClip->x)/(lEClip->x - lBClip->x);
         lBClip->x = x1;
      } else if (code1 & M3D_CODE_BELOW) { // lB->y < y1
         lBClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(y1 - lBClip->y)/(lEClip->y - lBClip->y));
         lBClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y1 - lBClip->y)/(lEClip->y - lBClip->y);
         lBClip->y = y1;
      } else if (code1 & M3D_CODE_RIGHT) { // lBClip->x > x2
         lBClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(x2 - lBClip->x)/(lEClip->x - lBClip->x));
         lBClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x2 - lBClip->x)/(lEClip->x - lBClip->x);
         lBClip->x = x2;
      } else if (code1 & M3D_CODE_ABOVE) { // lBClip->y > y2
         lBClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(y2 - lBClip->y)/(lEClip->y - lBClip->y));
         lBClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y2 - lBClip->y)/(lEClip->y - lBClip->y);
         lBClip->y = y2;
      }
      code1 = _m3xyGetPointCode(lBClip, x1, y1, x2, y2);
      if (code1 & code2) { // Line lays outside rectangle
         return M3D_OUTSIDE;
      }

      if (code2 & M3D_CODE_LEFT) {         // lEClip->x < x1
         lEClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(x1 - lBClip->x)/(lEClip->x - lBClip->x));
         lEClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x1 - lBClip->x)/(lEClip->x - lBClip->x);
         lEClip->x = x1;
      } else if (code2 & M3D_CODE_BELOW) { // lEClip->y < y1
         lEClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(y1 - lBClip->y)/(lEClip->y - lBClip->y));
         lEClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y1 - lBClip->y)/(lEClip->y - lBClip->y);
         lEClip->y = y1;
      } else if (code2 & M3D_CODE_RIGHT) { // lEClip->x > x2
         lEClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(x2 - lBClip->x)/(lEClip->x - lBClip->x));
         lEClip->y = lBClip->y + (lEClip->y - lBClip->y)*(x2 - lBClip->x)/(lEClip->x - lBClip->x);
         lEClip->x = x2;
      } else if (code2 & M3D_CODE_ABOVE) { // lEClip->y > y2
         lEClip->z = 1 /
                     (1/lBClip->z + (1/lEClip->z - 1/lBClip->z)*(y2 - lBClip->y)/(lEClip->y - lBClip->y));
         lEClip->x = lBClip->x + (lEClip->x - lBClip->x)*(y2 - lBClip->y)/(lEClip->y - lBClip->y);
         lEClip->y = y2;
      }
      code2 = _m3xyGetPointCode(lEClip, x1, y1, x2, y2);
   }
   return rc;
}

/*************************************************************
* m3dClipLSegNearFar()
*
* Clip line segment by near/far plane
* IN:  lB, lE        - line segment
*      nearPl, farPl - distances to near & far plane
* OUT: lB, lE        - clipped line segment
* RET: M3D_INSIDE, M3D_OUTSIDE, M3D_ISECT (clip retcode)
*************************************************************/
int m3dClipLSegNearFar (m3dV *_lB, m3dV *_lE, float nearPl, float farPl)
{
   m3dV   *lB, *lE;
   int    rc;

   // Swap lB & lE if lE is less than lB
   if (_lB->z > _lE->z) {
      lB = _lE;
      lE = _lB;
   } else {
      lB = _lB;
      lE = _lE;
   }
   rc = M3D_INSIDE;

   // Check near flane
   if (lB->z < nearPl) {
      if (lE->z < nearPl) {
         // Line doesn't belong near-far area
         return M3D_OUTSIDE;
      }
      // Clip lB point by near plane
      lB->x = lB->x + (lE->x - lB->x)*(nearPl - lB->z)/(lE->z - lB->z);
      lB->y = lB->y + (lE->y - lB->y)*(nearPl - lB->z)/(lE->z - lB->z);
      lB->z = nearPl;
      rc = M3D_ISECT;
   }

   if (lE->z > farPl) {
      if (lE->z > farPl) {
         // Line doesn't belong near-far area
         return M3D_OUTSIDE;
      }
      // Clip lE point by far plane
      lE->x = lB->x + (lE->x - lB->x)*(farPl - lB->z)/(lE->z - lB->z);
      lE->y = lB->y + (lE->y - lB->y)*(farPl - lB->z)/(lE->z - lB->z);
      lE->z = farPl;
      rc = M3D_ISECT;
   }
   return rc;
}

/*************************************************************
* _m2dGetPointCode()
* _m3xyGetPointCode()
*
* Calculate point code (belong point rect)
* IN : point          - point
*      x1, y1, x2, y2 - clipping rectangle
* RET: M3D_CODE_XXX (point code)
*************************************************************/
static short _m2dGetPointCode(m2dV *point, float x1, float y1, float x2, float y2)
{
   short code = 0;

   if (point->x < x1) code |= M3D_CODE_LEFT;
   if (point->y < y1) code |= M3D_CODE_BELOW;
   if (point->x > x2) code |= M3D_CODE_RIGHT;
   if (point->y > y2) code |= M3D_CODE_ABOVE;
   return code;
}

static short _m3xyGetPointCode (m3dV *point, float x1, float y1, float x2, float y2)
{
   short code = 0;

   if (point->x < x1) code |= M3D_CODE_LEFT;
   if (point->y < y1) code |= M3D_CODE_BELOW;
   if (point->x > x2) code |= M3D_CODE_RIGHT;
   if (point->y > y2) code |= M3D_CODE_ABOVE;
   return code;
}

//
// End-of-file M3D_CLIP.CPP
//
